package com.fanshuai.algorithms.datastructure.priorityqueue;

import java.util.Random;

/**
 * 排序稳定性：如果列表中有2个相等的元素，排序前和排序后相等元素的前后顺序不变，排序为稳定排序；否则为不稳定排序
 *
 * 冒泡排序：稳定排序  只存在相邻2个元素的交换
 * 插入排序：稳定排序  只存在相邻2个元素的交换
 * 简单选择排序：不稳定排序  存在任意元素的交换
 *
 * 快排：不稳定排序  存在任意元素的交换
 * 归并排序：稳定排序  归并的过程是稳定的
 * 堆排序：不稳定排序  存在任意元素的交换
 *
 */
public class HeapSort {
    /**
     * 堆排序
     * @param a
     */
    public static void heapSort(int[] a) {
        int k = (a.length - 1) / 2;

        //构造极大堆
        for (int i = k; i >= 0; i--) {
            sink(a, i, a.length - 1);
        }

        //极大堆跟节点为最大元素，每次将根节点跟最后一个元素交换，同时缩小极大堆规模，做下沉操作
        int N = a.length - 1;
        while (N > 0) {
            swap(a, 0, N);
            N--;
            sink(a, 0, N);
        }
    }

    /**
     * 极大堆下沉
     * @param a
     * @param i
     * @param n
     */
    private static void sink(int[] a, int i, int n) {
        while (2 * i + 1 <= n) {
            int k = 2 * i + 1;
            if (2 * i + 1 < n && a[k] < a[k + 1]) {
                k = k + 1;
            }
            if (a[i] < a[k]) {
                swap(a, i, k);
                i = k;
            } else {
                break;
            }
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 快排
     * @param a
     */
    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }

    private static void quickSort(int[] a, int start, int end) {
        if (start >= end) {
            return;
        }

        int p = partition(a, start, end);
        quickSort(a, start, p - 1);
        quickSort(a, p + 1, end);
    }

    private static int partition(int[] a, int start, int end) {
        int random = random(start, end);
        swap(a, random, end);  //将随机位置的元素跟末尾元素交换s

        int i = start - 1, j = end;
        int base = a[end];

        while (i <= j) {
            while (a[++i] < base && i < end) {
                ;
            }
            while (a[--j] > base && j > start) {
                ;
            }

            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }

        /**
         * 结束循环有2种s情况：
         * i==j: a[i] == a[j] == base
         * i>j:  a[i]> base, a[j] < base，此时需要将i和end位置交换元素
         */
        swap(a, i, end);
        return i;
    }

    private static int random(int start, int end) {
        Random random = new Random(System.currentTimeMillis());
        int r = random.nextInt(end - start + 1);
        return start + r;
    }

    /**
     * 归并排序
     * @param a
     */
    public static void mergeSort(int[] a) {
        int[] help = new int[a.length];
        System.arraycopy(a, 0, help, 0, a.length);

        mergeSort(a, help, 0, a.length - 1);
    }

    /**
     * 归并排序 分治法实现
     * 将[start, end]问题拆分为[start, mid]和[mid+1, end]子问题，按二分法平均拆分
     * 然后将2个子问题通过特定方式合并为问题的解
     * @param a
     * @param help
     * @param start
     * @param end
     */
    private static void mergeSort(int[] a, int[] help, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(a, help, start, mid);
        mergeSort(a, help, mid + 1, end);

        merge(a, help, start, mid, end);
    }

    private static void merge(int[] a, int[] help, int start, int mid, int end) {
        int i = start, j = mid + 1;
        for (int k = start; k <= end; k++) {
            if (i > mid) {
                help[k] = a[j++];
            } else if (j > end) {
                help[k] = a[i++];
            } else if (a[i] <= a[j]) { //<=保证稳定排序
                help[k] = a[i++];
            } else {
                help[k] = a[j++];
            }
        }

        System.arraycopy(help, start, a, start, end - start + 1);
    }

    public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a1 = {1, 6, 12, 6, 3, 9, 32, 19, 110, 224};
        int[] a2 = {1, 2, 3, 4, 5, 9, 7, 6, 8};
        int[] a3 = {23, 32, 45, 23, 14, 56, 91, 18};

        int[][] a = new int[3][];
        a[0] = a1;
        a[1] = a2;
        a[2] = a3;

        for (int[] aa : a) {
            //heapSort(aa);
            //insertionSort(aa);
            //quickSort(aa);
            mergeSort(aa);
            for (int i = 0; i < aa.length; i++) {
                System.out.print(aa[i] + " ");
            }
            System.out.println();
        }
    }
}
